PImage img;//load image
int xdim = 1024;//sets an integer for the x dimension
int ydim = 768;//sets an integer for the y dimension
int tdim = (xdim * ydim);//sets an integer for the total amount of pixels (width times height)
int sav = 1;//numbering system for the saved image file



void setup () {
  img = loadImage("1.jpg");//loads the image
  size (img.width*2,img.height);//size of the document, dependant on the size of the image
  image (img,xdim,0);
  
}
color [] pixel = new color [tdim]; //create an array the size of tdim, these pixels are based on the colors from the original image
float [] ave = new float [tdim];//float an array of tdim floats, that is the average value of each pixel 



void draw () {
  float r;
  float g;
  float b;// the color variables

  img.loadPixels();//loads the pixel information from the image
  for (int i = 0; i < ydim; i++) {
    for (int j = 0; j < xdim; j++) {//these two for statements cycle through the entire amount of pixels
      int loc = j + i*xdim;//this arranges the pixels into a one dimensional index
      
      r = red (img.pixels [loc]);
      g = green (img.pixels [loc]);
      b = blue (img.pixels [loc]);//assigns the variables to the particular color and location of each pixel from the original image
      
      pixel[loc] = color(r,g,b);//fills the pixel array with the color from the image
    }
  }
  
  
  for (int i = 0; i < tdim; i++) {
    ave [i] = ((red (img.pixels [i])) + (green (img.pixels [i])) + (blue (img.pixels [i])))/3;
  } //for statement that goes through each pixel and averages all 3 colors to calculate the value of the pixel
  
  quicksort (0,tdim-1);//calls the function quicksort which sorts the color value and alters the corresponding elements of the pixel array
  
  for(int i = 0; i < xdim; i++) {
    for(int j = 0; j < ydim; j++) {//for statements that cycles through each pixel and outputs the new ordered array of pixels
      int loc = i + (j*ydim);//this arranges it into a one dimensional index
      
      stroke(pixel[loc]);//sets the color of each individual pixel based on the array
      point(i,j);//outputs a single pixel based on the x,y coordinates

    
    }
  }
   save ("art" + sav + ".png");//saves the file as a png image
   noLoop();//prevents the program from looping and continuously rewriting the saved file
}

void quicksort(int low, int high) { //creates a function that will sort based on an algorithm that uses midpoints to sort

  int bottom = low, top = high - 1, part_index;//initializes variables which point to the elements of the array which are being compared
  float part_value;  //mid-point value
   if (low < high) { //checks the validity of low and high. Prevents the algorithm from changing data if incorrect values are provided
     if (high == (low + 1)) {  //base case: high and low are adjacent, thus the array being sorted is of length two
       if (ave[low] > ave[high]){  //if the two elements are out of order, switch them
	 swap_int(high, low); //calls the function which switches the elements
       }
     } else { //recursive case: the array is longer than length two and must be further divided
       part_index = (int)((low + high) / 2); //determines the mid-point index of the array
       part_value = ave[part_index]; //this is the mid-point value
       swap_int(high, part_index); //swaps the high value with the mid-point value
       do { //the do-while loop traverses the top down and bottom up of the array simultaneously
	 while ((ave[bottom] <= part_value) && (bottom <= top)){ //Continue moving up the array from the bottom until a value is found to be greater than the partition value
	   bottom++;//increments the bottom pointer
         } 
         while ((top>=0) && (ave[top] >= part_value) && (bottom <= top)){ //Continue moving down the array from the top untill a value is found to be less than the partition
	   top--;//decrements the bottom pointer
         }

	 if (bottom < top) { //if the bottom and top pointers have not converged, both have found values which are out of order and need to be switched
	   swap_int(bottom, top);
         }
       } while (bottom < top); //do while loop continues until the bottom and top pointers have converged; at this point, the entire array has been sorted according to the partition value
       swap_int(bottom, high);//partition element is switched to its final position
       quicksort(low, bottom - 1);//recursive call to sort the bottom half
       quicksort(bottom + 1, high);//recursive call to sort the top half
    }
  }
}

void swap_int(int n1, int n2){//helper function for quicksort which swaps two elements in the array with the indicies n1 and n2;
  float temp;//temporary placeholder variable
  temp = ave[n1];//the value to be switched is placed in the temporary variable
  ave[n1] = ave[n2];//the new value replaces the original value
  ave[n2] = temp;//the original value is retreived from the temporary variable
  
  color temp2;//temporary placeholder variable
  temp2 = pixel[n1];//the value to be switched is placed in the temporary variable
  pixel[n1] = pixel[n2];//the new value replaces the original value
  pixel[n2] = temp2;//the original value is retreived from the temporary variable

}